package one.three.fourtyTwo;

import java.util.Iterator;
import java.util.NoSuchElementException;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Stack<Item> implements Iterable<Item> {
	private Node<Item> first;
	private int n;

	private static class Node<Item> {
		private Item item;
		private Node next;
	}

	public Stack() {
		first = null;
		n = 0;
	}

	public Stack(Stack<Item> s) {
		Item[] tmp = (Item[]) new Object[s.size()];
		Node<Item> c = s.first;
		int i = 0;
		while (c != null) {
			tmp[i] = c.item;
			i++;
			c = c.next;
		}

		for (i = tmp.length-1; i >=0; i--) {
			push(tmp[i]);
		}

	}

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		return n;
	}

	public void push(Item item) {
		Node<Item> oldfirst = first;
		first = new Node<Item>();
		first.item = item;
		first.next = oldfirst;
		n++;
	}

	public Item pop() {
		if (isEmpty())
			throw new NoSuchElementException();
		Item item = first.item;
		first = first.next;
		n--;
		return item;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (Item item : this) {
			s.append(item);
			s.append(" ");
		}
		return s.toString();
	}

	@Override
	public Iterator<Item> iterator() {
		return new LinkedIterator(first);
	}

	private class LinkedIterator implements Iterator<Item> {
		private Node<Item> current;

		public LinkedIterator(Node<Item> first) {
			current = first;
		}

		public boolean hasNext() {
			return current != null;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

		@Override
		public Item next() {
			if (!hasNext())
				throw new NoSuchElementException();
			Item item = current.item;
			current = current.next;
			return item;
		}

	}

	public static void mains(String[] args) {
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			System.out.println(item);
		}
		System.out.println("END");
	}

	public static void main(String[] args) {
		Stack<String> s0 = new Stack<String>();
		s0.push("a");
		s0.push("b");
		s0.push("c");

		Stack<String> s1 = new Stack<String>(s0);
		
		System.out.println(s0);
		System.out.println(s1);
		
		s0.push("d");
		s1.push("e");
		
		System.out.println(s0);
		System.out.println(s1);
	}

}